package main

import "fmt"

func main() {
	arr := []int{3, 5, 9, 2, 4}
	fmt.Println(partition(arr, 0, len(arr)-1))
	fmt.Println(arr)

}

// {3, 5, 9, 2, 4}
// {3, 4, 9, 2, 5}

/*
*
i0;j0, i=j ;i++;j++
i1;j1,
*/
func partition(arr []int, start, end int) int {
	pivot := arr[end]
	var i = start
	for j := start; j < end; j++ {
		if arr[i] < pivot {
			if !(i == j) {
				arr[i], arr[j] = arr[j], arr[i]
			}
			i++
		}
	}
	arr[i], arr[end] = arr[end], arr[i]
	fmt.Println(arr)
	return i
}
